//
//  DLinkList.hpp
//  DLinkList
//
//  Created by chenyh on 2021/2/4.
//

#ifndef DLinkList_hpp
#define DLinkList_hpp

#include <iostream>
template <typename DataType> class DoubleList;
//双向链表结点定义
template <typename DataType> class DoubleListNode
{
private:
    friend class DoubleList<DataType>;  //声明链表类为友元类
    DoubleListNode():m_pprior(NULL),m_pnext(NULL){} //无参数构造函数，将指针初始化为null;
    //带参数构造函数初始化数据域和指针域
    DoubleListNode(const DataType item,DoubleListNode<DataType> * pprior = NULL,DoubleListNode<DataType> *next = NULL):m_data(item),m_pprior(pprior),m_pnext(next){}
    //析构函数
    ~DoubleListNode() {
        m_pprior = NULL;
        m_pnext = NULL;
    }
    
    DataType m_data;            //数据域
    DoubleListNode *m_pprior;   //指向前驱结点的指针域
    DoubleListNode *m_pnext;    //指向后继结点的指针域
public:
    DataType getData();         //获取结点内的数据值
};

//获取结点中的数据
template <typename DataType>
DataType DoubleListNode<DataType>::getData() {
    return this->m_data;
}

//双向链表定义
template <typename DataType>
class DoubleList {
public:
    DoubleList()
    {
        head = new DoubleListNode<DataType>();
    }
    ~DoubleList()
    {
        cleanDoubleLink();
        delete head;
    }
public:
    void cleanDoubleLink();         //清空双向链表
    int getLength();                //获取链表长度
    DoubleListNode<DataType> *findNode(int i = 0); //寻找第i个结点
    DoubleListNode<DataType> *findData(DataType item);//寻找具有给定值数据的结点
    bool insertNode(DataType item,int i = 0);   //在第i个结点后插入新结点
    bool removeNode(int i = 0);                 //删除第i个结点
    DataType getData(int i = 0);                //获取第i个结点的数据
private:
    DoubleListNode<DataType> *head;
};

template <typename DataType>
void DoubleList<DataType>::cleanDoubleLink() {
    DoubleListNode<DataType> *pmove = head->m_pnext,*pdel;
    while (pmove != NULL) { //一次删除头指针后面的结点
        pdel = pmove;
        pmove = pdel->m_pnext;
        delete pdel;
    }
    head->m_pnext = NULL;
}

template <typename DataType>
int DoubleList<DataType>::getLength() {
    int count = 0;
    DoubleListNode<DataType> *pmove = head->m_pnext;
    while (pmove != NULL) {
        pmove = pmove->m_pnext;
        count++;
    }
    return count;
}

template <typename DataType>
DoubleListNode<DataType> * DoubleList<DataType>:: findNode(int n) {
    if (n < 1) {
        std::cout<<"非有效位置"<<std::endl;
        return NULL;
    }
    DoubleListNode<DataType> *pmove = head->m_pnext;
    for (int i = 1; i < n; i++) {
        pmove = pmove->m_pnext;
        if (pmove==NULL) {
            std::cout<<"不存在指定结点"<<std::endl;
            return NULL;
        }
    }
    return pmove;
}
template <typename DataType>
bool DoubleList<DataType>::insertNode(DataType item,int n){
    int i;
    if (n < 1) {
        std::cout<<"插入位置无效"<<std::endl;
        return 0;
    }
    //创建新结点，设置游标指针
    DoubleListNode<DataType> *newnode = new DoubleListNode<DataType>(item),*pmove=head;
    if (newnode == NULL) {
        std::cout<<"内存分配失败，新结点无法创建"<<std::endl;
        exit(1);
    }
    for (i = 1; i < n; i++) {
        pmove=pmove->m_pnext;
        if (pmove==NULL && i < n-1) {
            std::cout<<"超出链表长度，插入位置无效！"<<std::endl;
            return 0;
        }
    }
    newnode->m_pnext = pmove->m_pnext;
    if (pmove->m_pnext != NULL) {
        pmove->m_pnext->m_pprior = newnode;
    }
    newnode->m_pprior = pmove;
    pmove->m_pnext = newnode;
    return 1;
    
}

template <typename DataType>
bool DoubleList<DataType>::removeNode(int n){
    if (n < 1 || n>getLength()) {
        std::cout<<"位置不合法！"<<std::endl;
        return false;
    }
    DoubleListNode<DataType> *pmove = head->m_pnext,*pdel;
    for (int i = 1; i < n
         ; i++) {
        pmove = pmove->m_pnext;
        if (pmove == NULL) {
            std::cout<<"超出了链表范围！"<<std::endl;
            return false;
        }
    }
    //删除结点
    pdel=pmove;
    pmove->m_pprior->m_pnext = pdel->m_pnext;
    pmove->m_pnext->m_pprior = pdel->m_pprior;
    delete pdel;
    return true;
}

template <typename DataType>
DataType DoubleList<DataType>::getData(int n) {
    if (n < 1 || n>getLength()) {
        std::cout<<"位置不合法！"<<std::endl;
        exit(1);
    }
    DoubleListNode<DataType> * pmove = head->m_pnext;   //设置游标指针
    for (int i = 1; i < n; n++) {
        pmove = pmove->m_pnext;
        if (pmove == NULL) {
            std::cout<<"指定结点不存在！"<<std::endl;
            exit(1);
        }
    }
    if (pmove == NULL) {
        std::cout<<"结点不存在！"<<std::endl;
        return NULL;
    }
    return pmove->m_data;
}

template <typename DataType>
DoubleListNode<DataType> * DoubleList<DataType>::findData(DataType item) {

    DoubleListNode<DataType> *pmove = head->m_pnext; //设置游标指针
    if (pmove == NULL) {
        std::cout<<"链表是空表！"<<std::endl;
        exit(1);
    }
    while (pmove->getData() != item) {
        pmove=pmove->m_pnext;
        if (pmove == NULL) {
            std::cout<<"没有所查找的结点！"<<std::endl;
            exit(1);
        }
    }
    return pmove;
}
    
#endif /* DLinkList_hpp */
